#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author:zhengxin
@file: 030_josephus_problem.py
@time: 2024/12/20  17:00
# @describe:
"""

"""
有n个人围成一圈，顺序排号。
    从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位
    
这是一个经典的 约瑟夫环（Josephus problem）问题。
"""

# 解法 1：模拟解法。 通过模拟每个人报数并退出，直到只剩下一个人。
def josephus_problem(n):
    # 创建一个从1到n的列表，表示 n个人
    people = list(range(1, n+1))

    # 从第一个人开始报数
    index = 0

    while len(people) > 1:     # 当剩余的人数大于1时
        # 计算报到3的人（每次跳跃2个位置，实际上是数到3的人）
        index = (index + 2) % len(people)

        # 退出找个人
        people.pop(index)

    # 返回最后留下的人
    return people[0]

n = 7
print(f"最后留下的是原来第 {josephus_problem(n)} 号的人")



# 解法 2：递推公式。用迭代来计算最终的结果。
def josephus_formula(n):
    # 当只有一个人时，编号是 0
    result = 0
    for i in range(2, n+1):
        result = (result + 3) % i
    return result + 1       # 转换回从1开始的编号

n = 7
print(f"最后留下的是原来第 {josephus_formula(n)} 号的人")